package airthmetic.exercise.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class _102_二叉树的层序遍历 {
    // BFS
    public static List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<List<Integer>>();
        }

        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        List<List<Integer>> res = new ArrayList();
        while(!queue.isEmpty()){
            int n = queue.size();
            List<Integer> levels = new ArrayList();
            for(int i=0; i<n; i++){
                TreeNode node = queue.poll();
                levels.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            res.add(levels);
        }

        return res;
    }

    // DFS
    public static List<List<Integer>> levelOrder2(TreeNode root) {
        if(root == null){
            return new ArrayList<List<Integer>>();
        }

        List<List<Integer>> res = new ArrayList();
        recur(root,0,res);
        return res;
    }

    public static void recur(TreeNode node, int level, List<List<Integer>> res){
        if(node == null){
            return;
        }

        if(level > res.size() - 1){
            List<Integer> nums = new ArrayList();
            res.add(nums);
        }
        List<Integer> nums = res.get(level);
        nums.add(node.val);

        recur(node.left,level+1,res);
        recur(node.right,level+1,res);

    }
}
